Theoretically, the number of memory locations which can be accessed by a central processor in a simple computer system is limited by the number of bits in the address word used to access the memory. In such a system it is often possible to ensure a one-to-one correspondence between a particular address bit configuration and a physical memory location and, therefore, the address bit configuration generated by the processor may be applied directly to the memory to gain access to information stored within.
In other systems, however, it is desirable that the processor generate addresses which are different from the physical addresses at which the information is stored in the memory. Some type of translation process is therefore required. Such a translation process may be advantageous in order to provide protection for the operating system programs and user programs or to provide more efficient memory storage for systems operating with certain programs.
Translation becomes even more important in multi-tasking or multi-process systems in which two or more tasks or processes are resident in the system memory at the same time and where one process runs during the time while the other is temporarily suspended. In such a multi-tasking system it is possible for each task to separately access the entire memory space through the same processor address bits and therefore such a system can efficiently utilize a memory which may be many times larger than the theoretical size limit dictated by the processor address word size alone. Since each process necessarily uses common address designations, some type of translation is essential to separate the address spaces of the individual programs.
Memory systems in which an address translation is required are typically called virtual memory systems. The processor generates a "logical" or "virtual" address which is provided to a memory management unit which contains a translator. The output of the translator is the physical address which is, in fact, used to access the memory. Typically, the translator is a table (designated a "page table") which is itself located in memory. Therefore, an ordinary memory access requires, in fact, two accesses to memory in order to produce desired data. The first memory access reads the translator table and the second access reads data from the physical address obtained from the translator table.
In order to obtain reasonable translation efficiency, all virtual memory systems use a high-speed translation buffer to perform the most frequently used address translations. A translation buffer is typically a high-speed hardware store which contains a table (commonly designated the "page table entry store") of selected entries from the translator table. During a memory access, a portion of the virtual address produced by the processor is used to index an entry in the page table entry store. If the entry is valid (designated a "hit"), it contains the corresponding physical address which is available at hardware speeds. If a valid translation is not located in the page table entry store (a "miss") then additional hardware is activated which performs a normal memory access to the translator table stored in memory, obtains and writes the physical address data into the proper page table entry for use at a later time.
In the conventional virtual memory system, each location in the page table entry store can be indexed by several virtual addresses. Therefore, it is necessary to separate page table entry store locations which contain data valid for a particular virtual address from those which contain data meaningless for a the virtual address. This separation is conventionally done by utilizing additional bits commonly known as "tag" bits. The tag bit portion or field of a virtual address word usually consists of several highest-order bits. These bits are stored in a "tag store" associated with the page table entry store at corresponding address locations. When an access is made to the page table entry store, the tag bits located in the tag store are simultaneously indexed and are compared to the tag field of the virtual address. A match or hit indicates that the page table entry is valid.
Such a prior art translation operation works well in general purpose systems. However, in systems primarily designed for multi-processing or multi-tasking, interprogram protection is a primary necessity in order to ensure operational integrity of each process and its associated data. This protection is normally achieved by using different sets of translations for each process. Therefore, even if each process uses common virtual addresses, the translation process will insure that both the process and its data will be located in a unique physical memory space.
To insure integrity in a virtual system which utilizes a translation buffer, the buffer must be cleared or "flushed" (by invalidating all entries) during a context switch to prevent one program from invading the address space of its predecessor. A significant penalty time is therefore incurred because the buffer must first be flushed and then slowly refilled by "misses" as the process runs. For most general purpose systems these penalty times are not critical in the overall operation of the system.
However, in systems designed especially for "real-time" applications, response time is often critical to the success or failure of the operation. In addition, in a real-time system the amount of task swapping is often greatly increased over normal, general purpose operations and therefore the penalty time incurred in flushing the translation buffer and then refilling it contributes significantly to a long response time.
Some memory management units utilize a different type of operation than that described above in order to avoid some of the penalty time normally associated with context switches. In this latter type of memory management system, each processor task is assigned a unique process number or address space number and the translations for all of the running tasks in the system are simultaneously stored in the translation buffer store. The memory of the system is artificially divided into segments of variable length. Each entry in the translation buffer store is a segment "descriptor" which includes the physical address of the segment in memory, the associated virtual address and the address space number of the task using that address together with masks for determining which bits in the virtual address and the address space number are significant (the masking operation determines the effective segment length). In addition, the corresponding virtual address together with a mask indicating which bits are significant in that address are also stored with the physical address information.
In such a system the translation buffer entries are not indexed directly by means of the virtual address. Instead, the virtual address produced by the processor and the virtual address stored in each memory location are masked and compared. In addition, both the processor number or address space number produced by the processor during each task and the stored address space number are masked and compared. If there are matches in both the address space numbers and the virtual addresses, then the corresponding physical address information is masked and used as the physical address.
One advantage of such a prior art system is that the address translations for all tasks are simultaneously stored in the buffer store and a flush and refill of the buffer store is not required during a context switch. However, since the translation buffer store is not indexed directly from the virtual address but the virtual address and address space number are first masked by stored information and then compared to other stored information, each location in the translation buffer store must have two comparators associated with it. Therefore, a large amount of circuitry is required to process address translations. Large translation buffers are often required for real-time systems and this latter translation scheme typically uses a large amount of integrated circuit "real estate" and is subject to hardware faults and other problems.
It is therefore an object of the present invention to provide memory control circuitry suitable for use with virtual memory systems which is optimizied for use with multi-processing or multi-tasking systems.
It is another object of the invention to provide memory control circuitry which avoids the time penalty associated with flushing the translation buffer and refilling it during a context switch.
It is a further object of the invention to provide a memory control circuitry which is suitable for multi-tasking virtual memory system which does not require large amounts of repetitive circuitry.
It is yet another object of the present invention to provide a mechanism for preventing short programs from continually reusing the same portion of the address translation buffer yet allowing large programs to use the entire translation buffer, if necessary.